1114E - Arithmetic Progression - CodeForces Solution

#include <bits/stdc++.h>
#include <random>
//#pragma GCC optimize ("Ofast, no-stack-protector, unroll-loops, fast-math, O3")
using namespace std;
using ll = long long;
using ld = long double;
#define el '\n'
#define mp(x, y) make_pair(x,y)
#define popcount __builtin_popcountll
#define ios ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
const int mod = 998244353;
const int INF = 1e7;
const ld pi = acos(-1);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

ll rand(ll l, ll r) {
    return uniform_int_distribution<ll>(l, r)(rng);
}

int main() {
    int n;
    cin >> n;
    int l = 0, r = 1e9, cnt = 60;
    while(l <= r){
        int mid = (l + r) >> 1;
        cnt--;
        cout << "> " << mid << endl;
        int num;cin >> num;
        if(num){
            l = mid + 1;
        }else{
            r = mid - 1;
        }
    }
    int mx = l;
    vector<int> arr;
    set<int>s;
    while(cnt-- && s.size() < n){
        int idx = rand(1, n);
        while(s.count(idx))
            idx = rand(1, n);
        s.insert(idx);
        cout << "? " << idx << endl;
        int num;
        cin >> num;
        arr.push_back(num);
    }
    sort(arr.begin(), arr.end());
    arr.push_back(mx);
    int g = 0;
    for(int i = 0;i < arr.size() - 1;i++){
        for(int j = i + 1;j < arr.size();j++){
            g = __gcd(arr[j] - arr[i], g);
        }
    }
    int start = mx - g * (n - 1);
    cout << "! " << start << " " << g << endl;
}